package top.fengleifeng.question;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年11月23日 12:00 下午
 */
public class Num452用最少数量的箭引爆气球 {

    class Solution {

        public int findMinArrowShots(int[][] points) {
            int result = 0;
            if (points.length <= 0) {
                return 0;
            }
            Arrays.sort(points, (a1, a2) -> {
                if (a1[0] > a2[0]) {
                    return 1;
                } else if (a1[0] == a2[0]) {
                    if (a1[1] > a2[1]) {
                        return 1;
                    } else if (a1[1] == a2[1]) {
                        return 0;
                    } else {
                        return -1;
                    }
                } else {
                    return -1;
                }
            });

            int start = points[0][0], end = points[0][1];
            int count = 1;
            for (int i = 1; i < points.length; i++) {
                if (points[i][0] <= end) {
                    start = Math.max(points[i][0], start);
                    end = Math.min(points[i][1], end);
                } else {
                    count++;
                    start = points[i][0];
                    end = points[i][1];
                }
            }
            return count;
        }
    }

    public static void main(String[] args) {
//        int[][] ints = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
//        int[][] ints = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
        int[][] ints = {{-2147483646, -2147483645}, {2147483646, 2147483647}};
        int minArrowShots = new Num452用最少数量的箭引爆气球().new Solution().findMinArrowShots(ints);
        System.out.println(minArrowShots);
    }
}
